【week14】397. Integer Replacement 解题报告

397. Integer Replacement

题目

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with *n*/2.
2. If n is odd, you can replace n with either *n* + 1 or *n* - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

解题报告

题意很简单，给定一个整数 $K$ ，定义两种操作：奇数时 $K=K+1$ 或 $K=K-1$，偶数时$K=K/2$，问要多少次操作才能让 $K=1$ 成立。

刚看到这题时，我第一反应是用动规，因为状态转移方程很容易就能想出来：

$$DP[i]=\begin{cases}DP[i/2]+1, & \text{if }n\text{ is even} \\min(DP[i+1],DP[i-1])+1, & \text{if }n\text{ is odd} \end{cases}$$

也很容易写出来了：

// DP: Memory Limit Exceeded
class Solution {
public:
    int integerReplacement(int n) {
        if (n <= 2) return n - 1; 
        vector<int> dp(n + 2);
        for (int i = 3; i < n + 1; i += 2) {
            dp[i - 1] = dp[(i - 1) / 2] + 1;
            dp[i + 1] = dp[(i + 1) / 2] + 1;
            dp[i] = min(dp[i - 1], dp[i + 1]) + 1;
        }
        return dp[n];
    }
};

可见，当 test case 为大整数时，会超出内存限制，这相当于不能使用任何数组。只能另寻他路。

然后我又想到，是否可以用贪心的思想，当 $K$ 为偶数时，操作必然是除 2，那么对于每一个操作中间产生的偶数，都可以直接把它不断除二知道它为奇数为止，再加上其操作次数。假设每一个偶数 $K$ 最后变成的奇数为 $toOdd(K)$，那对于一个奇数 $K$，如果 $toOdd(K+1)<toOdd(K-1)$，则直接采用操作 $K=K+1$，具体的数学原理我也说不清，只能说当此时 $toOdd(K-1)$ 要达到 $toOdd(K+1)$ 附近必然需要更多操作。

确定这一算法之后代码也很快可以写出来：

// Time Limit Exceeded
class Solution {
public:
    int getEvenTime(int &k) {	// 算出除2的次数顺便算出 toOdd(k)
        int ret = 0;
        while (!(k & 1)) {
            k /= 2;
            ++ret;
        }
        return ret;
    }
    int integerReplacement(int n) {
        int plus, sub, pt, st;
        int even = getEvenTime(n);        
        while (n != 1) {
            plus = n + 1;
            sub = n - 1;
            pt = getEvenTime(plus);
            st = getEvenTime(sub);
            if (plus < sub) {
                n = plus;
                even += pt + 1;
            } else {
                n = sub;
                even += st + 1;
            }
        }
        return even;
    }
};

然而这次超时了，审视自己的算法，每次都要去算两次 $toOdd$，但是其中一次其实没有意义，这浪费了大量的时间，是否可以只算一次？

因为两个数只差了 2 ，所以比较两个 $toOdd$，实际上是比较谁更能除 2，在二进制数中比较的就是谁低位的 0 更多，这让我想起了之前看过的树状数组中的 lowbit ，这是求一个二进制数最后一个 1 的位置的操作，可以表示为 x & -x。那我不就可以根据这个求出谁更能除 2 吗？

于是便有了最终的答案，其中需要注意的是，当 $K$ 为 3 时，其前后恰好是 2 和 4，这时这个判断条件会失效，要额外判断一下。

Solution

class Solution {
public:
    int integerReplacement(int n) {
        if (n == INT_MAX) return 32;	// 溢出
        int ans = 0;
        while (n != 1) {		// toOdd
            while (!(n & 1)) {
                ++ans;
                n >>= 1;
            }
            if (n <= 3) return ans + n - 1;		// 临界条件
            if (((n + 1) & -(n + 1)) < ((n - 1) & -(n - 1)))
                --n;
            else
                ++n;
            ++ans;
        }
        return ans;
    }
};